/// @tags: Sqrt
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using std::min;

namespace BlueQuantum {

int const N = 4e4 + 5, SIZ = 2e2, M = SIZ + 5;

template <typename T>
inline T &read(T &x) {
  x = 0;
  bool f = false;
  short ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = true;
    ch = getchar();
  }
  while (isdigit(ch)) x = x * 10 + (ch ^ '0'), ch = getchar();
  if (f) x = -x;
  return x;
}

int n, m;
int tmpbuk[N], buk[N], a[N], hash[N], L[N], R[N], id[N], sum[M][N], vis[N];

struct Node {
  int num, cnt;
  Node() : num(0), cnt(0) {}
} pre[M][M];

inline void prework() {
  int blk = (n - 1) / SIZ + 1;
  for (int i = 1; i <= blk; ++i) L[i] = R[i - 1] + 1, R[i] = i * SIZ;
  R[blk] = n;
  for (int i = 1; i <= blk; ++i) {
    memset(buk, 0, sizeof(buk));
    Node tmp;
    for (int j = i; j <= blk; ++j) {
      for (int k = L[j]; k <= R[j]; ++k) {
        id[k] = j;
        buk[a[k]]++;
        if (buk[a[k]] > tmp.cnt) {
          tmp.num = a[k];
          tmp.cnt = buk[a[k]];
        } else if (buk[a[k]] == tmp.cnt)
          tmp.num = min(tmp.num, a[k]), tmp.cnt = buk[a[k]];
      }
      pre[i][j] = tmp;
    }
  }
  for (int i = 1; i <= blk; ++i) {
    for (int j = 1; j <= n; ++j) sum[i][a[j]] = sum[i - 1][a[j]];
    for (int j = L[i]; j <= R[i]; ++j) sum[i][a[j]]++;
  }
}

inline int main() {
  read(n), read(m);
  for (int i = 1; i <= n; ++i) hash[i] = read(a[i]);
  std::sort(hash + 1, hash + n + 1);
  *hash = std::unique(hash + 1, hash + n + 1) - hash - 1;
  for (int i = 1; i <= n; ++i) a[i] = std::lower_bound(hash + 1, hash + *hash + 1, a[i]) - hash;
  prework();
  for (int i = 1, l, r, ans = 0; i <= m; ++i) {
    l = (read(l) + ans - 1) % n + 1;
    r = (read(r) + ans - 1) % n + 1;
    if (l > r) std::swap(l, r);
    int posL = id[l], posR = id[r];
    if (posR - posL <= 1) {
      ans = 0;
      for (int j = l; j <= r; ++j) tmpbuk[a[j]] = 0;
      for (int j = l; j <= r; ++j) {
        tmpbuk[a[j]]++;
        if (tmpbuk[a[j]] > tmpbuk[ans]) ans = a[j];
        else if (tmpbuk[a[j]] == tmpbuk[ans])
          ans = min(ans, a[j]);
      }
    } else {
      ans = pre[posL + 1][posR - 1].num;
      tmpbuk[ans] = 0, vis[ans] = 0;
      for (int j = l; j <= R[posL]; ++j) tmpbuk[a[j]] = 0, vis[a[j]] = false;
      for (int j = L[posR]; j <= r; ++j) tmpbuk[a[j]] = 0, vis[a[j]] = false;
      for (int j = l; j <= R[posL]; ++j) tmpbuk[a[j]]++;
      for (int j = L[posR]; j <= r; ++j) tmpbuk[a[j]]++;
      int ansnum, anscnt = 0;
      for (int j = l; j <= R[posL]; ++j)
        if (!vis[a[j]]) {
          vis[a[j]] = true;
          int val = tmpbuk[a[j]] + sum[posR - 1][a[j]] - sum[posL][a[j]];
          if (anscnt < val) anscnt = val, ansnum = a[j];
          else if (anscnt == val)
            ansnum = min(ansnum, a[j]);
        }
      for (int j = L[posR]; j <= r; ++j)
        if (!vis[a[j]]) {
          vis[a[j]] = true;
          int val = tmpbuk[a[j]] + sum[posR - 1][a[j]] - sum[posL][a[j]];
          if (anscnt < val) anscnt = val, ansnum = a[j];
          else if (anscnt == val)
            ansnum = min(ansnum, a[j]);
        }
      if (anscnt > tmpbuk[ans] + pre[posL + 1][posR - 1].cnt) ans = ansnum;
      else if (anscnt == tmpbuk[ans] + pre[posL + 1][posR - 1].cnt)
        ans = min(ans, ansnum);
    }
    printf("%d\n", ans = hash[ans]);
  }
  return 0;
}

}  // namespace BlueQuantum

int main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("/tmp/CodeTmp/testdata.in", "r", stdin);
  freopen("/tmp/CodeTmp/testdata.out", "w", stdout);
#else
  freopen("P4168 [Violet]蒲公英.in", "r", stdin);
  freopen("P4168 [Violet]蒲公英.out", "w", stdout);
#endif
#endif

  return BlueQuantum::main();
}